基本概念

此处仅讨论比特差错(1<->0)

1. 分类 -> 检错编码和纠错编码
2. 码距(海明距离) -> 两个码字在对应位置上取值不同的比特数量 -> 可以通过异或运算得到新的码, 新的码中1的位数即为码距
3. 编码集的码距 -> 任意两个有效码字之间码距的最小值
4. 差错控制理论 -> 编码方案的检错能力与纠错能力与码距l的关系为$l=d+c+1,且d\geq c$其中, d为检错位数, c为纠错位数, 纠错能力不超过检错能力, 因此有边界条件c=0以及d=c

检错编码

冗余编码技术, 在信息位(有效数据)发送前, 按照特定规则附加冗余位(检验位), 确保码数符合规则再发送; 接收方使用同样规则来校验

奇偶检验码

1. 奇检验码 -> 附加检验位后, 码字中1的位数为奇数
2. 偶检验码 -> 附加检验位后, 码字中1的位数为偶数

只能检测奇数位错误

循环冗余码

-> Cyclic Redundancy Code, CRC

1. 生成多项式(G(x)对应二进制码) 阶数为最高项次数r, 最多有r+1项, 最高位和最低位必须为0
2. 用信息位计算, 生成冗余校验信息(帧检验序列,FCS) 计算方式为模2除法(本质上是吧竖式除法换成异或)
3. 附加在原始数据(信息位)之后
4. 接收方使用相同的模二触发检验, 为0则认为传输无差错, 否则重传/丢弃

在工程实践中常认为, 被数据链路层接受的帧, 几乎可以确定在传输中为发生差错

纠错编码

• 最常见的纠错码 -> 海明码
• 信息位n位和检验位k位按一定规则排列
• 每个校验位对应一个校验组(通常采用偶校验), 从而实现检测甚至确定错误位置实现单比特纠错

海明码的构造

1. 确定总位数(n,k满足)$2^{k}\geq n+k+1$通过代值即可求k
2. 检验位放在海明码的$2^{i-1}$位置上(海明码按照1~n+k的下标排列, 可以从小到大或者反过来)
3. 分组检验 -> 将每一个信息位的海明位号进行换算成二进制, 需要用到二进制为1的位对应的检验位来检验(海明码位也是对应的)
4. 检验位取值 -> 相同检验位分为同一组, 同一组异或计算得到检验位取值

海明码的纠错

1. 同一分组(包括检验位)共同计算异或得到当前分组的检测值, 如果为0则正确
2. 多个分组拼起来成为0或者错误位的序号
3. 一般来说, 开始有一位奇偶校验用于确定有奇数位错还是有偶数位错, 来纠错或者重传

总结

1. 注意码距的相关概念